SYTHESIS AND COMPLEXITY OF CELLULAR CIRCUITRY ASYMPTOTICALLY OPTIMAL BY RELIABILITY

Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), alehina@pnzgu.ru
Rybakov Andrey Valentinovich, Postgraduate student, Penza State University (40 Krasnaya street, Penza, Russia), dm@pnzgu.ru

519.718

Background. The work relates to one of the most important divisions of mathematical cybernetics – the theory of synthesis, reliability and complexity of control systems. Such models of discrete functions computing as functional elements circuits are well-known. These circuits, consisting of absolutely reliable or unreliable elements, have been studied for a long time; researchers have obtained multiple results for them. However in real circuits it is necessary to take into account not just functional elements, but also circuit’s geometry. Thereby, the authors suggested a model of cellular circuits consisting of functional elements, where the model is represented in the form of a rectangle, divided into cells, which contain circuit elements having certain sizes and occupying certain area. Cellular elements may be both functional, i.e. realizing some function from their inputs, and commutational, which transmit signals to a next element with possible alteration of direction. The study suggests that commutational elements are absolutely reliable, and inverse malfunctions occur independently on any of two functional element outputs with the same probability. Such circuits are a natural mathematical model of integral circuits and, therefore, have multiple applications in various fields of science and technology, and also appear to be relevant for research. The aim of the work is to build cellular circuits, asymptotically optimal by reliability, and to estimate complexity thereof.
Materials and methods. In order to build cellular circuits, asymptorically optimal by reliability, the authors used a method based on the method of synthesizing functional element circuits, asymptotically optimal by reliability. For this method the researchers built cellular circuits, proved the corresponding theorems on upper and lower reliability estimates and estimated the built circuits.
Results. The authors suggested a method of synthesis of cellular circuits, asymptotically optimal by reliability, and obtained upper and lower reliability estimates of the said circuits. For the first time the authors proved the estimate of complexity of cellular circuits, asymptotically optimal by reliability.
Conclusions. In order to build cellular circuits, asymptotically optimal by reliability, it is possible to use the methods of synthesis of functional element circuits, asymptotically optimal by reliability.

cellular circuits, functional and commutational elements, synthesis and complexity of reliable cellular circuits.

1. von Neuman J. Automata studies. Ed. by Shannon C., Mc. Carthy J. Princeton University Press, 1956.
2. Ortyukov S. I. Trudy seminara po diskretnoy matematike i ee prilozheniyam (Moskva, 27–29 yanvarya 1987 g.) [Proceedigns of the seminar on discrete mathematics and application thereof (Moscow, 27-29 January 1987)]. Moscow: Izd-vo Mosk. un-ta, 1989, pp. 166 – 168.
3. Uhlig D. Fundamentals of Computation Theory. Intern. sonf. FCT'87 (Kazan, June 1987). Proc. Berlin: Springer-Verl., 1987, pp. 462–469.
4. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physics and mathematics sciences]. 2008, no. 4, pp. 2–16.
5. Alekhina M. A., Aksenov S. I. Diskretnaya matematika i ee prilozheniya: materialy IX Mezhdunar. seminara (Moskva, 18–23 iyunya 2007 g.) [Discrete mathematics and applications thereof: proceedings of IX International seminar (commemorating 75th jubilee of O.B. Lupanov) (Moscow, 18-23 June 2007)]. Moscow: Izd-vo mekh.-mat. fak-ta MGU, 2007, pp. 56–59.
6. Rybakov A. V. Otkrytye innovatsii – vklad molodezhi v razvitie regiona: sb. materialov regional'nogo molodezhnogo foruma (Rossiya, g. Penza, 22 noyabrya 2013 g.) [Open innovations – youth’s contribution into regional development (Russia, Penza, 22 November 2013)]. Penza : Izd-vo PGU, 2013, pp. 164–165.
7. Rybakov A. V. Universitetskoe obrazovanie: sb. st. KhVIII Mezh-dunar. nauch.-metod. konf. (MKUO–2014) (Penza, 10–11 aprelya 2014 g.) [University education: collected articles of XVIII International scientific and methodological conference (Penza, 10-11 April 2014)]. Penza: Izd-vo PGU, 2014, pp. 310–311.
8. Kravtsov S. S. Problemy kibernetiki [Problems of cybernetics].Issue19.Moscow:Nauka,1967,pp.285–292.
9. Ulesova A. Yu. Slozhnost' realizatsii bulevykh funktsiy v nekotorykh modelyakh kletochnykh skhem [Complexity of Boolean functions realization in some models of cellular circuits]. Moscow: MGU im. Lomonosova, fakul'tet VMiK, kafedra matematicheskoy kibernetiki, 2010, 25 p.
10. Alekhina M. A., Lakomkina A. E., Il'ina Yu. D. Otkrytye innovatsii – vklad molodezhi v razvitie regiona: sb. materialov regional'nogo molodezhnogo foruma (Rossiya, g. Penza, 22 noyabrya 2013 g.) [Open innovations – youth’s contribution into regional development (Russia, Penza, 22 November 2013)]. Penza: Izd-vo PGU, 2013, pp. 11–12.